package class066;

import java.util.Arrays;

// 解码方法
// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
// 例如，"11106" 可以映射为："AAJF"、"KJF"
// 注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F"
// 这是由于 "6" 和 "06" 在映射中并不等价
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
// 题目数据保证答案肯定是一个 32位 的整数
// 测试链接 : https://leetcode.cn/problems/decode-ways/
class Solution {
public:
    int numDecodings1(string s) {

        // return f1(s, 0);

        vector<int> dp(s.size(), -1);
        return f2(s, 0, dp);
    }

    // int f1(string& s, int i, vector<int>&)
    // 暴力
    int f1(string& s, int i) {
        if (i == s.size())
            return 1;

        int ans;
        // s[i........]
        if (s[i] == '0') {
            ans = 0;
        } else {
            ans = f1(s, i + 1);
            if (i + 1 < s.size() &&
                ((s[i] - '0') * 10 + (s[i + 1] - '0')) <= 26) {
                ans += f1(s, i + 2);
            }
        }

        return ans;
    }

    // 记忆化搜索
    int f2(string& s, int i, vector<int>& dp) {
        if (i == s.size())
            return 1;

        if (dp[i] != -1)
            return dp[i];

        int ans;

        if (s[i] == '0') {
            return 0;
        } else {
            ans = f2(s, i + 1, dp);

            if (i + 1 < s.size() &&
                ((s[i] - '0') * 10 + (s[i + 1] - '0')) <= 26) {
                ans += f2(s, i + 2, dp);
            }
        }

        dp[i] = ans;
        return ans;
    }

    //严格依赖动态位置
    int numDecodings3(string s) {

        // return f1(s, 0);

        vector<int> dp(s.size() + 1, 0);
        int n = s.size();
        dp[n] = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 < s.size() &&
                    ((s[i] - '0') * 10 + (s[i + 1] - '0')) <= 26) {
                    dp[i] += dp[i + 2];
                }
            }
        }

        return dp[0];
    }

    int numDecodings(string s) {

        //dp[n+1]
        int nextnext = 0;
        //dp[n]
        int next = 1;

        int cur = 0;
        int n = s.size();
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                cur = 0;
            } else {
                cur = next;
                if (i + 1 < n &&
                    ((s[i] - '0') * 10 + (s[i + 1] - '0')) <= 26) {
                    cur += nextnext;
                }
            }

            nextnext = next;
            next = cur;
        }

        return next;
    }
};